package com.hot100;

import java.util.HashMap;
import java.util.Map;

public class Solution124 {
    int res = Integer.MIN_VALUE;

    public int maxPathSum(TreeNode root) {
        max(root);
        return res;
    }

    public int max(TreeNode root) {
        if (root == null) return 0;
        int left = max(root.left);
        int right = max(root.right);
        int tmp = root.val + Math.max(0, left) + Math.max(0, right);
        res = Math.max(res, tmp);
        return root.val + Math.max(0, Math.max(left, right));
    }
}
